package com.example.array;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * 示例 1：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * <p>
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * <p>
 * 输出：false
 */
public class Leetcode74_SearchMatrix {
    public static void main(String[] args) {
        int[][] matrix = {
                {1,   3,  5,  7},
                {10, 11, 16, 20},
                {23, 30, 34, 60},
        };
        int[][] matrix2 = {
                {1,3}
        };

        int[]matrix3 = {1};
//        System.out.println(searchMatrix(matrix2, 3));
        System.out.println(searchMatrix(matrix2, 3));


    }

    /**
     * 解法一:逐行行用二分查找
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        // 逐行进行二分查找
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i][0] > target){ // 当前行的最小值是否大于target, 则不需要进行二分查找
                return false;
            } else {
                if (binarySearchRow(matrix[i], target, 0 , matrix[i].length - 1)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static boolean binarySearchRow(int[] row, int target, int start, int end) {
        if (end < start || row[start] > target || row[end] < target)
            return false;
        int mid = (start + end) / 2;

        if (row[mid] == target)
            return true;
        if (row[mid] > target)
            return binarySearchRow(row, target, start, mid - 1);

        return binarySearchRow(row, target, mid + 1, end);

    }

    /**
     * 方式二：把二维数组matrix[m][n]当做一维数组处理 array[m*n],一行接一行
     * matrix中row行column列 对应array中下标为 row*n+column
     * array 中的下标x换算 matrix 行列的关系为：row=x/n column=x%n
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null)
            return false;
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 || n == 0 || matrix[0][0] > target || matrix[m - 1][n -1] < target)
            return false;

        int left = 0, right = m * n - 1;
        int midIndex, midData;
        // 二分查找
        while (left <= right) {
            midIndex = (left + right) / 2;
            if (matrix[midIndex / n][midIndex % n] == target)
                return true;

            if (matrix[midIndex / n][midIndex % n] > target) {
                right = midIndex - 1;
            } else {
                left = midIndex + 1;
            }
        }
        return false;
    }

}
